package MonotoneStack;
/*
 * 接雨水
 */
import java.util.Deque;
import java.util.LinkedList;

public class lc42 {

    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int len = height.length;
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            if (height[stack.peek()] > height[i]) {
                stack.push(i);
            } else if (height[stack.peek()] == height[i]) {
                stack.pop();
                stack.push(i);
            } else {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int temp = stack.pop();
                    if (!stack.isEmpty()) {
                        int h = Math.min(height[stack.peek()], height[i]) - height[temp];
                        int w = i - stack.peek() - 1;
                        if (h * w > 0) res += h * w;
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }

}
